from GA import GA
import random
from copy import deepcopy
import numpy as np


def calculate_distance(distance_matrix, order):
    distance_sum = 0.0
    for num in range(len(order)):
        distance_sum += distance_matrix[order[num], order[(num + 1) % (len(order))]]
    return distance_sum


class GAMTSP(GA):
    def __init__(self, data, pc=0.7, pm=0.02, pop_size=None, selection_type='WES', crossover_type='PMX',
                 mutation_type='swap', parameter=None, sale_num=3, score_type='max', local_search=False, depot=None):
        self.sale_num = sale_num
        if sale_num < 2:
            raise TypeError("illegal sale_num")
        self.max_len_evolve_list = []
        self.depot = self.center_city(data) if depot == 'center' else depot
        if self.depot and (self.depot < 0 or self.depot > len(data.cities)):
            raise TypeError("illegal depot")
        super(GAMTSP, self).__init__(data, pc, pm, pop_size, selection_type, crossover_type, mutation_type, parameter,
                                     score_type, local_search)

    def __repr__(self):

        print(f'N:{self.n};POP:{self.pop_size};Pc:{self.pc};Pm{self.pm};LS:{self.local_search}')
        print(f'GA:{self.__class__.__name__};m:{self.sale_num};goal:{self.score_type}')
        if self.depot:
            print(f'Depot:{self.depot}')

    def center_city(self, data):
        city_x, city_y = data.x[1:], data.y[1:]
        center_x, center_y = 1 / 2 * (max(city_x) + min(city_x)), 1 / 2 * (max(city_y) + min(city_y))
        dis = [(city_x[i] - center_x) ** 2 + (city_y[i] - center_y) ** 2 for i in range(len(city_x))]
        return dis.index(min(dis)) + 1

    def calculate_score(self, individual):
        self.eval += 1
        if self.score_type == 'sum':
            return self.distance(individual)
        elif self.score_type == 'max':
            return self.max_len(individual)
        elif self.score_type == 'sqrt':
            return self.multi_sqrt(individual)
        else:
            raise TypeError('undefined score_type')

    def distance(self, individual):
        target = individual.transform(self.sale_num, self.depot)
        return self.multi_distance(target)

    def max_len(self, individual):
        routes = individual.transform(self.sale_num, self.depot)
        sums = [calculate_distance(self.Distance, routes[i]) for i in range(len(routes))]
        return max(sums)

    def multi_sqrt(self, individual):
        target, sums = individual.transform(self.sale_num, self.depot), 0
        for r in target:
            sums = sums + (calculate_distance(self.Distance, r)) ** 2
        return sums

    def reduction(self, gene):
        return gene

    def LocalSearch(self, local_search=False):
        if self.local_search or local_search:
            for j in range(self.pop_size):
                temp = self.population[j].transform(self.sale_num, self.depot)
                for i in range(len(temp)):
                    temp[i] = self.twoopt_LS(temp[i])
                temp = self.reduction(temp)
                self.population[j].gene = temp.gene
            temp = self.best.transform(self.sale_num, self.depot)
            for i in range(len(temp)):
                temp[i] = self.twoopt_LS(temp[i])
            temp = self.reduction(temp)
            self.best.gene = temp.gene

    def optimize(self, eval_set=None, gen_set=None, display=True, count=None):
        self.best = deepcopy(self.population[0])
        self.judge()
        if eval_set is None:
            eval_set = self.n * 1000
        while self.eval <= eval_set:
            self.generation_new()
            best_distance = self.distance(self.best)
            best_max = self.max_len(self.best)
            if display:
                if count is not None:
                    print(f'\rNo.{str(count).zfill(2)}: {self.generation}  {best_distance:.4f}  {best_max:.4f}', end='')
                else:
                    print(f'\r{self.generation}  {best_distance:.4f}  {best_max:.4f}', end='')
            self.evolve_list.append(best_distance)
            self.max_len_evolve_list.append(best_max)
            if gen_set is not None and self.generation >= gen_set:
                break
        if display:
            print('')
        return self.best

    def draw_route(self, data, plt, individual, show_text=False, show_route=True):
        if show_route:
            print('\n')
        route = deepcopy(individual.transform(self.sale_num, self.depot))
        if self.depot and show_route:
            print('depot:', self.depot)
            plt.scatter(x=self.city_x[self.depot], y=self.city_y[self.depot], c='r', edgecolors='k', marker='*',
                        s=50, zorder=999)
        route = [i + [i[0]] for i in route]
        if show_route:
            print('best route:', route)
        for r in route:
            data.draw(plt, route=r, show_text=show_text)


class GA1C(GAMTSP):
    def __init__(self, data, pc=0.7, pm=0.02, pop_size=None, selection_type='WES', crossover_type='PMX',
                 mutation_type='swap', parameter=None, sale_num=3, score_type='max', local_search=False, depot=None):
        super(GA1C, self).__init__(data, pc, pm, pop_size, selection_type, crossover_type, mutation_type, parameter,
                                   sale_num, score_type, local_search, depot)
        self.gene_len = self.n + self.sale_num - 2 if self.depot else self.n + self.sale_num - 1
        self.name = __class__.__name__

    class onechromosome(object):
        def __init__(self, gene=None):
            self.gene = gene
            self.score = -1

        def transform(self, sale_num, depot):
            target = [[]]
            if depot:
                for k in range(len(self.gene)):
                    if self.gene[k] < len(self.gene) - sale_num + 3:
                        target[-1].append(self.gene[k])
                    else:
                        target.append([])
            else:
                for k in range(len(self.gene)):
                    if self.gene[k] < len(self.gene) - sale_num + 2:
                        target[-1].append(self.gene[k])
                    else:
                        target.append([])
            if depot:
                for i in range(len(target)):
                    target[i].append(depot)
            return target

        def verification(self, sale_num, depot):
            target = self.transform(sale_num, depot)
            for pos in target:
                if len(pos) < 2:
                    return False
            return True

    def population_init(self):
        self.population = []
        self.gene_len = self.n + self.sale_num - 2 if self.depot else self.n + self.sale_num - 1
        while len(self.population) < self.pop_size:
            gene = list(range(1, self.n + self.sale_num))
            if self.depot:
                gene.remove(self.depot)
            random.shuffle(gene)
            individual = self.onechromosome(gene)
            if individual.verification(self.sale_num, self.depot):
                self.population.append(individual)

    def crossover(self):
        population_new = []
        for i in range(int(self.pop_size / 2)):
            if random.random() < self.pc:
                parent1, parent2 = self.population[i * 2], self.population[i * 2 + 1]
                child1, child2 = self.choose_crossover(parent1.gene, parent2.gene)
                child1, child2 = self.onechromosome(child1), self.onechromosome(child2)
                if child1.verification(self.sale_num, self.depot):
                    population_new.append(child1)
                if child2.verification(self.sale_num, self.depot):
                    population_new.append(child2)
            else:
                child1, child2 = self.population[i * 2], self.population[i * 2 + 1]
                population_new.append(child1)
                population_new.append(child2)
        while len(population_new) < self.pop_size:
            population_new.append(self.population[random.randint(0, self.pop_size - 1)])
        self.population = population_new

    def mutation(self):
        for i in range(self.pop_size):
            if random.random() < self.pm:
                temp = deepcopy(self.population[i])
                temp.gene = self.choose_mutation(temp.gene)
                if temp.verification(self.sale_num, self.depot):
                    self.population[i].gene = temp.gene

    def reduction(self, gene):
        if self.depot:
            for i in range(len(gene)):
                index = gene[i].index(self.depot)
                gene[i] = gene[i][index:] + gene[i][:index] if index else gene[i]
                gene[i] = gene[i][1:]
        gene_new = gene[0]
        for i in range(len(gene) - 1):
            gene_new.append(self.n + i + 1)
            gene_new += gene[i + 1]
        return self.onechromosome(gene_new)


class GA2C(GAMTSP):
    def __init__(self, data, pc=0.7, pm=0.02, pop_size=None, selection_type='WES', crossover_type='PMX',
                 mutation_type='swap', parameter=None, sale_num=3, score_type='max', local_search=False, depot=None):
        super(GA2C, self).__init__(data, pc, pm, pop_size, selection_type, crossover_type, mutation_type, parameter,
                                   sale_num, score_type, local_search, depot)
        self.name = __class__.__name__

    class twochromosome(object):
        def __init__(self, gene=None, salesmen=None):
            self.gene = gene
            self.salesman = salesmen
            self.score = -1

        def transform(self, sale_num, depot):
            target = [[] for _ in range(sale_num)]
            for k in range(len(self.gene)):
                target[self.salesman[k]].append(self.gene[k])
            if depot:
                for i in range(len(target)):
                    target[i].append(depot)
            return target

        def verification(self, sale_num, depot):
            target = self.transform(sale_num, depot)
            for pos in range(len(target)):
                if len(target[pos]) < 2:
                    return False
            return True

    def population_init(self):
        self.population = []
        self.gene_len = self.n - 1 if self.depot else self.n
        salesman = []
        for k in range(self.sale_num - 1):
            salesman = salesman + [k for _ in range(int(self.gene_len / self.sale_num))]
        while len(salesman) < self.gene_len:
            salesman.append(self.sale_num - 1)
        while len(self.population) < self.pop_size:
            gene = list(range(1, self.n + 1))
            if self.depot:
                gene.remove(self.depot)
            random.shuffle(gene)
            individual = self.twochromosome(gene, salesman)
            self.population.append(individual)

    def crossover(self):
        population_new = []
        for i in range(int(self.pop_size / 2)):
            if random.random() < self.pc:
                parent1, parent2 = self.population[i * 2], self.population[i * 2 + 1]
                child1, child2 = self.choose_crossover(parent1.gene, parent2.gene)
                temp1, temp2 = [], []
                for pos in range(self.gene_len):
                    temp1.append(parent1.salesman[parent1.gene.index(child1[pos])])
                    temp2.append(parent2.salesman[parent2.gene.index(child2[pos])])
                child1, child2 = self.twochromosome(child1, temp1), self.twochromosome(child2, temp2)
                population_new.append(child1)
                population_new.append(child2)

            else:
                child1, child2 = self.population[i * 2], self.population[i * 2 + 1]
                population_new.append(child1)
                population_new.append(child2)
        while len(population_new) < self.pop_size:
            population_new.append(self.population[random.randint(0, self.pop_size - 1)])
        self.population = population_new

    def mutation(self):
        for i in range(self.pop_size):
            if random.random() < self.pm:
                self.population[i].gene = self.choose_mutation(self.population[i].gene)
            if random.random() < self.pm:
                pos = random.randint(0, self.gene_len - 1)
                temp = deepcopy(self.population[i])
                temp.salesman[pos] = random.randint(0, self.sale_num - 1)
                self.population[i] = temp if temp.verification(self.sale_num, self.depot) else self.population[i]

    def reduction(self, gene):
        gene_new, sale_new = [], []
        if self.depot:
            for i in range(len(gene)):
                gene[i].remove(self.depot)
        for i in range(len(gene)):
            for j in range(len(gene[i])):
                gene_new.append(gene[i][j])
                sale_new.append(i)
        return self.twochromosome(gene_new, sale_new)


class GA2PC(GAMTSP):
    def __init__(self, data, pc=0.7, pm=0.02, pop_size=None, selection_type='WES', crossover_type='PMX',
                 mutation_type='swap', parameter=None, sale_num=3, score_type='max', local_search=False, depot=None):
        super(GA2PC, self).__init__(data, pc, pm, pop_size, selection_type, crossover_type, mutation_type, parameter,
                                    sale_num, score_type, local_search, depot)
        self.name = __class__.__name__

    class twopartchromosome(object):
        def __init__(self, gene=None, salesmen=None):
            self.gene = gene
            self.salesman = salesmen
            self.score = -1

        def transform(self, sale_num=None, depot=None):
            target = [self.gene]
            for i in self.salesman:
                target.append(target[0][0:i])
                target[0] = target[0][i::]
            target = target[1::]
            if depot:
                for i in range(len(target)):
                    target[i].append(depot)
            return target

        def verification(self, sale_num=None, depot=None):
            for i in self.salesman:
                if i < 2:
                    return False
            if sum(self.salesman) == len(self.gene):
                return True
            else:
                return False

    def population_init(self):
        self.population = []
        self.gene_len = self.n - 1 if self.depot else self.n
        while len(self.population) < self.pop_size:
            gene = list(range(1, self.n + 1))
            if self.depot:
                gene.remove(self.depot)
            random.shuffle(gene)
            salesman = []
            for i in range(self.sale_num - 1):
                salesman.append(int(self.gene_len / self.sale_num))
            salesman.append(self.gene_len - sum(salesman))
            individual = self.twopartchromosome(gene, salesman)
            if individual.verification(self.sale_num, self.depot):
                self.population.append(individual)

    def crossover(self):
        population_new = []
        for i in range(int(self.pop_size / 2)):
            if random.random() < self.pc:
                parent1, parent2 = self.population[i * 2], self.population[i * 2 + 1]
                if random.random() < 2:
                    child1, child2 = self.choose_crossover(parent1.gene, parent2.gene)
                    salesman1, salesman2 = self.ARC1(parent1.salesman, parent2.salesman)
                    child1, child2 = self.twopartchromosome(child1, salesman1), self.twopartchromosome(child2,
                                                                                                       salesman2)
                else:
                    child1, child2 = self.TCX(parent1, parent2), self.TCX(parent2, parent1)
                if child1.verification(self.sale_num, self.depot):
                    population_new.append(child1)
                if child2.verification(self.sale_num, self.depot):
                    population_new.append(child2)
            else:
                child1, child2 = self.population[i * 2], self.population[i * 2 + 1]
                population_new.append(child1)
                population_new.append(child2)
        while len(population_new) < self.pop_size:
            population_new.append(self.population[random.randint(0, self.pop_size - 1)])
        self.population = population_new

    def mutation(self):
        for i in range(self.pop_size):
            if random.random() < self.pm:
                self.population[i].gene = self.choose_mutation(self.population[i].gene)
            if random.random() < self.pm:
                temp = deepcopy(self.population[i])
                temp.salesman = self.ARM(temp.salesman)
                if temp.verification(self.sale_num, self.depot):
                    self.population[i].salesman = temp.salesman

    def ARC1(self, parent1, parent2):
        offspring1, offspring2 = [], []
        alpha = random.random()
        for pos in range(self.sale_num - 1):
            offspring1.append(int(alpha * parent1[pos] + (1 - alpha) * parent2[pos]))
            offspring2.append(int(alpha * parent2[pos] + (1 - alpha) * parent1[pos]))
        offspring1.append(self.n - sum(offspring1))
        offspring2.append(self.n - sum(offspring2))
        return offspring1, offspring2

    def ARC2(self, parent1, parent2):
        offspring1, offspring2 = [], []
        alpha = random.random()
        for pos in range(self.sale_num - 1):
            offspring1.append(int(parent1[pos] + alpha * (parent2[pos] - parent1[pos])))
            offspring2.append(int(parent2[pos] + alpha * (parent1[pos] - parent2[pos])))
        offspring1.append(self.n - sum(offspring1))
        offspring2.append(self.n - sum(offspring2))
        return offspring1, offspring2

    def ARM(self, gene):
        index1, index2 = random.randint(0, self.sale_num - 1), random.randint(0, self.sale_num - 1)
        temp = min(int(gene[index1] * random.random() * 0.5), gene[index1] - 2)
        gene[index1] -= temp
        gene[index2] += temp
        return gene

    def TCX(self, parent1, parent2):
        index1, index2 = [], []
        child, choice, remains = [], [], []
        for i in range(self.sale_num):
            index1.append(random.randint(0, parent1.salesman[i] - 2))
            index2.append(random.randint(index1[-1] + 1, parent1.salesman[i] - 1))
            child.append(parent1.gene[sum(parent1.salesman[0:i]) + index1[i]:sum(parent1.salesman[0:i]) + index2[i]])
            choice += child[-1]
        for i in parent2.gene:
            if i in choice:
                continue
            remains.append(i)
        for i in range(self.sale_num - 1):
            index = random.randint(0, len(remains) - 1)
            child[i] = child[i] + remains[0:index]
            remains = remains[index::]
        child[-1] = child[-1] + remains
        salesman = [len(child[i]) for i in range(len(child))]
        while len(child) > 1:
            child[-1] += child[0]
            child = child[1::]
        return self.twopartchromosome(child[0], salesman)

    def reduction(self, gene):
        if self.depot:
            for i in range(len(gene)):
                gene[i].remove(self.depot)
        gene_new, sale_new = [], []
        for i in range(len(gene)):
            for j in range(len(gene[i])):
                gene_new.append(gene[i][j])
            sale_new.append(len(gene[i]))
        return self.twopartchromosome(gene_new, sale_new)


class GAMC(GAMTSP):
    def __init__(self, data, pc=0.7, pm=0.02, pop_size=None, selection_type='WES', crossover_type='GGASS',
                 mutation_type='swap', parameter=None, sale_num=3, score_type='max', local_search=False, depot=None):
        super(GAMC, self).__init__(data, pc, pm, pop_size, selection_type, crossover_type, mutation_type, parameter,
                                   sale_num, score_type, local_search, depot)
        self.gene_len = len(self.cities)
        self.name = __class__.__name__

    class multichromosome(object):
        def __init__(self, gene=None):
            self.gene = gene
            self.score = -1

        def transform(self, sale_num=None, depot=None):
            if depot:
                gene_new = deepcopy(self.gene)
                for i in range(len(gene_new)):
                    gene_new[i].append(depot)
                return gene_new
            else:
                return self.gene

        def verification(self, sale_num=None, depot=None):
            for pos in range(len(self.gene)):
                if len(self.gene[pos]) < 1 or (len(self.gene[pos]) < 2 and not depot):
                    return False
            return True

    def population_init(self):
        self.population = []
        self.gene_len = self.n - 1 if self.depot else self.n
        while len(self.population) < self.pop_size:
            gene = list(range(1, self.n + 1))
            if self.depot:
                gene.remove(self.depot)
            random.shuffle(gene)
            gene, salesman = [gene], []
            for i in range(self.sale_num - 1):
                salesman.append(int(self.gene_len / self.sale_num) * (i + 1))
            k = 1
            while len(gene) < len(salesman) + 1:
                gene.append(gene[0][salesman[-k]:len(gene[0])])
                gene[0] = gene[0][0:salesman[-k]]
                k = k + 1
            individual = self.multichromosome(gene)
            if individual.verification(depot=self.depot):
                self.population.append(individual)

    '''
    def mutation(self):
        for i in range(self.pop_size):
            temp = deepcopy(self.population[i])
            for j in range(len(self.population[i].gene)):
                if random.random() < self.pm:
                    choice = random.choice([0, 1, 2])
                    temp.gene[j] = self.swap(temp.gene[j]) if choice == 0 else temp.gene[j]
                    temp.gene[j] = self.twoopt(temp.gene[j]) if choice == 1 else temp.gene[j]
                    temp.gene[j] = self.insert(temp.gene[j]) if choice == 2 else temp.gene[j]
            temp.gene = self.transposition(temp.gene) if random.random() < self.pm else temp.gene
            self.population[i] = temp if temp.verification(depot=self.depot) else self.population[i]
    '''

    def transposition(self, gene):
        index1, index2 = random.randint(0, len(gene) - 1), random.randint(0, len(gene) - 1)
        while index1 == index2:
            index2 = random.randint(0, len(gene) - 1)
        index11, index21 = random.randint(0, len(gene[index1]) - 1), random.randint(0, len(gene[index2]) - 1)
        index12, index22 = random.randint(index11, len(gene[index1]) - 1), random.randint(index21,
                                                                                          len(gene[index2]) - 1)
        gene[index1], gene[index2] = gene[index1][:index11] + gene[index2][index21:index22] + gene[index1][index12::], \
                                     gene[index2][:index21] + gene[index1][index11:index12] + gene[index2][index22::]
        return gene

    def GGASS(self, parent1, parent2):
        child = []
        while len(child) < self.sale_num:
            parents = parent1 if random.randint(0, 1) else parent2
            rk = self.hope_tour(parents)
            for i in range(len(parents)):
                if len(parents[i]) < 2:
                    rk[i] = float('inf')
            r_max = parents[rk.index(min(rk))]
            if len(r_max) < 2:
                break
            child.append(r_max)
            parent1 = [self.remove_all(i, r_max) for i in parent1]
            parent1 = self.remove_all(parent1, [[]])
            parent2 = [self.remove_all(i, r_max) for i in parent2]
            parent2 = self.remove_all(parent2, [[]])
            if (not parent1) and (not parent2):
                break
        remain = []
        for i in parent1 + parent2:
            remain = remain + i
        remains = list(set(remain))
        random.shuffle(remains)
        child = self.insert_remains(remains, child)
        while len(child) < self.sale_num:
            child = self.GGASS_increase(child)
        return child

    def hope_tour(self, parents):
        if self.depot:
            if self.score_type == 'sum':
                return [calculate_distance(self.Distance, i + [self.depot]) / len(i) for i in parents]
            else:
                return [calculate_distance(self.Distance, i + [self.depot]) for i in parents]
        else:
            if self.score_type == 'sum':
                return [calculate_distance(self.Distance, i) / len(i) for i in parents]
            else:
                return [calculate_distance(self.Distance, i) for i in parents]

    def insert_remains(self, remains, child):
        for remain in remains:
            if random.random() < 0.95:
                num, pos = 0, 0
                best = self.Distance[child[0][-1]][remain] + self.Distance[remain][child[0][0]] - \
                       self.Distance[child[0][-1]][child[0][0]]
                for i in range(len(child)):
                    for j in range(len(child[i])):
                        sum_l = self.Distance[child[i][(j - 1 + len(child[i])) % len(child[i])]][remain] \
                               + self.Distance[remain][child[i][j]] - \
                               self.Distance[child[i][(j - 1 + len(child[i])) % len(child[i])]][child[i][j]]
                        if sum_l < best:
                            num, pos, best = i, j, sum_l
            else:
                num, pos = random.randint(0, len(child) - 1), 0
                best = self.Distance[child[num][-1]][remain] + self.Distance[remain][child[num][0]] - \
                       self.Distance[child[num][-1]][child[num][0]]
                for j in range(len(child[num])):
                    sum_l = self.Distance[child[num][(j - 1 + len(child[num])) % len(child[num])]][remain] \
                           + self.Distance[remain][child[num][j]] - \
                           self.Distance[child[num][(j - 1 + len(child[num])) % len(child[num])]][child[num][j]]
                    if sum_l < best:
                        pos, best = j, sum_l
            child[num].insert(pos, remain)
        return child

    def GGASS_increase(self, child):
        rk = self.hope_tour(child)
        for i in range(len(child)):
            if len(child[i]) < 4:
                rk[i] = 0
        r_max = child[rk.index(max(rk))]
        best_a, best_b = 0, 2
        best = self.Distance[r_max[-1]][r_max[2]] + self.Distance[r_max[0]][r_max[1]] \
               - self.Distance[r_max[-1]][r_max[0]] - self.Distance[r_max[2]][r_max[1]]
        for a in range(len(r_max)):
            for b in range(a, len(r_max)):
                if (b - a < 2) or (a + len(r_max) - b < 2):
                    continue
                else:
                    temp = self.Distance[r_max[(a - 1 + len(r_max)) % len(r_max)]][r_max[b]] + \
                            self.Distance[r_max[a]][r_max[(b - 1 + len(r_max)) % len(r_max)]] - \
                            self.Distance[r_max[(a - 1 + len(r_max)) % len(r_max)]][r_max[a]] - \
                            self.Distance[r_max[b]][r_max[(b - 1 + len(r_max)) % len(r_max)]]
                    if temp < best:
                        best_a, best_b, best = a, b, temp
        child.remove(r_max)
        child.append(r_max[best_a:best_b])
        child.append(r_max[best_b:] + r_max[:best_a])
        return child

    def crossover(self):
        population_new = []
        for i in range(int(self.pop_size / 2)):
            if random.random() < self.pc:
                parent1, parent2 = self.population[i * 2], self.population[i * 2 + 1]
                child1, child2 = self.choose_crossover(parent1, parent2)
                child1, child2 = self.multichromosome(child1), self.multichromosome(child2)
            else:
                child1, child2 = self.population[i * 2], self.population[i * 2 + 1]
            population_new.append(child1)
            population_new.append(child2)
        while len(population_new) < self.pop_size:
            population_new.append(self.population[random.randint(0, self.pop_size - 1)])
        self.population = population_new

    def choose_crossover(self, parent1, parent2):
        if self.crossover_type == 'GGASS':
            child1, child2 = self.GGASS(parent1.gene, parent2.gene), self.GGASS(parent1.gene, parent2.gene)
        elif self.crossover_type == 'EAX':
            child1, child2 = self.EAX(parent1, parent2)
        else:
            raise TypeError('undefined crossover')
        self.cross_count += 1
        return child1, child2

    def reduction(self, gene):
        if self.depot:
            for i in range(len(gene)):
                gene[i].remove(self.depot)
        return self.multichromosome(gene)

    def decrease(self, child):
        rk = [calculate_distance(self.Distance, i) for i in child]
        r_min = child[rk.index(min(rk))]
        child.remove(r_min)
        temp = deepcopy(child)
        temp[0] = child[0] + r_min
        best = self.multi_distance(temp)
        temp[0] = child[0]
        best_p = 0
        for pos in range(1, len(child) * 2):
            temp[int(pos / 2)] = r_min + child[int(pos / 2)] if pos % 2 else child[
                                                                                               int(pos / 2)] + r_min
            if self.multi_distance(temp) < best:
                best_p = pos
            temp[int(pos / 2)] = child[int(pos / 2)]
        child[int(best_p / 2)] = r_min + child[int(best_p / 2)] if best_p % 2 else child[int(best_p / 2)] + r_min
        return child

    def EAX(self, parent1, parent2, illegal_amend=True):
        if self.depot:
            pa1, pa2 = [r + [self.depot] for r in parent1.gene], [r + [self.depot] for r in parent2.gene]
            e1 = [[[r[i], r[(i + 1) % len(r)], 'p1'] for i in range(len(r))] for r in pa1]
            e2 = [[[r[i], r[(i + 1) % len(r)], 'p2'] for i in range(len(r))] for r in pa2]
        else:
            pa1, pa2 = parent1.gene, parent2.gene
            e1 = [[[r[i], r[(i + 1) % len(r)], 'p1'] for i in range(len(r))] for r in pa1]
            e2 = [[[r[i], r[(i + 1) % len(r)], 'p2'] for i in range(len(r))] for r in pa2]
        edge1, edge2 = [], []
        for i in e1:
            edge1 += i
        for i in e2:
            edge2 += i
        ab_set = self.edges2ABroute(edge1 + edge2)
        ab_set2 = self.remove_all([i if len(i[0]) < 3 else [] for i in ab_set], [[]])
        ab_set = self.remove_all([i if len(i[0]) > 2 else [] for i in ab_set], [[]])
        if illegal_amend:
            while ab_set2:
                choice, next_city, index, ab_setlist = ab_set2[0][0], -1, -1, [i[0] for i in ab_set]
                for city in choice:
                    for route in range(len(ab_setlist)):
                        if city in ab_setlist[route]:
                            index, next_city = route, city
                            break
                if index > -1:
                    pos = ab_set[index][0].index(next_city)
                    ab_set[index][0] = ab_set[index][0][0:pos] + [next_city] + [choice[1 - choice.index(next_city)]] + \
                                       ab_set[index][0][pos::]
                    ab_set2.remove(ab_set2[0])
                else:
                    ab_setlist = [i[0] for i in ab_set2[1::]]
                    for city in choice:
                        for route in range(len(ab_setlist)):
                            if city in ab_setlist[route]:
                                index = route
                                next_city = city
                                break
                    ab_set2[index][0] = [next_city] + [choice[1 - choice.index(next_city)]] + [next_city] + [
                        ab_set2[index + 1][0][1 - ab_set2[index + 1][0].index(next_city)]]
                    ab_set.append(ab_set2[index])
                    ab_set2.remove(ab_set2[index])
                    ab_set2.remove(ab_set2[0])
        e_set1, e_set2 = self.block(ab_set, parent1, parent2)
        e_set_edges1, e_set_edges2 = self.route2edges(e_set1, ab_circle=True), self.route2edges(e_set2, ab_circle=True)
        off_edge1, off_edge2 = deepcopy(edge1), deepcopy(edge2)
        for edge in e_set_edges1:
            if edge[-1] == 'p1':
                if edge in off_edge1:
                    off_edge1.remove(edge)
                else:
                    off_edge1.remove(edge[0:2][::-1] + [edge[-1]])
            else:
                off_edge1.append(edge)
        for edge in e_set_edges2:
            if edge[-1] == 'p1':
                off_edge2.append(edge)
            else:
                if edge in off_edge2:
                    off_edge2.remove(edge)
                else:
                    off_edge2.remove(edge[0:2][::-1] + [edge[-1]])
        off_edge1, off_edge2 = self.edges2route(off_edge1, ab_circle=True), self.edges2route(off_edge2, ab_circle=True)
        off = [[i[0] for i in off_edge1], [i[0] for i in off_edge2]]
        for num in range(len(off)):
            while 1:
                if self.big_circle(off[num]):
                    off[num] = self.GGASS_increase(off[num])
                else:
                    break
            if self.depot:
                for i in range(len(off[num])):
                    while self.depot in off[num][i]:
                        off[num][i].remove(self.depot)
                off[num] = self.remove_all(off[num], [[]])
            while len(off[num]) > self.sale_num:
                off[num] = self.decrease_circle(off[num])
            while len(off[num]) < self.sale_num:
                off[num] = self.GGASS_increase(off[num])
        return off[0], off[1]

    def block(self, ab_set, parent1=None, parent2=None, block_type='block'):
        if len(ab_set) < 1:
            return ab_set, ab_set
        else:
            if block_type == 'default':
                ab_set.sort(key=lambda x: len(x[0]), reverse=True)
                e_set = [ab_set[0]]
                for i in range(len(ab_set) - int(len(ab_set) / 2), len(ab_set)):
                    for city in ab_set[i][0]:
                        if city in e_set[0][0]:
                            e_set.append(ab_set[i])
                            break
                return e_set, e_set
            elif block_type == 'block':
                ab_set.sort(key=lambda x: len(x[0]), reverse=True)
                e_set = [ab_set[1]] if len(ab_set) > 1 else [ab_set[-1]]
                if self.depot:
                    pa1, pa2 = [r + [self.depot] for r in parent1.gene], [r + [self.depot] for r in parent2.gene]
                    e1 = [[[r[i], r[(i + 1) % len(r)], 'p1'] for i in range(len(r))] for r in pa1]
                    e2 = [[[r[i], r[(i + 1) % len(r)], 'p2'] for i in range(len(r))] for r in pa2]
                else:
                    pa1, pa2 = parent1.gene, parent2.gene
                    e1 = [[[r[i], r[(i + 1) % len(r)], 'p1'] for i in range(len(r))] for r in pa1]
                    e2 = [[[r[i], r[(i + 1) % len(r)], 'p2'] for i in range(len(r))] for r in pa2]
                off_edge1, off_edge2 = [], []
                for i in e1:
                    off_edge1 += i
                for i in e2:
                    off_edge2 += i
                e_set_edges = self.route2edges(e_set, ab_circle=True)
                e_set1, e_set2 = deepcopy(e_set), deepcopy(e_set)
                ab_set = ab_set[2:] if len(ab_set) > 2 else []
                for edge in e_set_edges:
                    if edge[-1] == 'p1':
                        if edge in off_edge1:
                            off_edge1.remove(edge)
                        else:
                            off_edge1.remove(edge[0:2][::-1] + [edge[-1]])
                        off_edge2.append(edge)
                    else:
                        if edge in off_edge2:
                            off_edge2.remove(edge)
                        else:
                            off_edge2.remove(edge[0:2][::-1] + [edge[-1]])
                        off_edge1.append(edge)
                off_edge1, off_edge2 = self.edges2route(off_edge1, ab_circle=True), self.edges2route(off_edge2, ab_circle=True)
                off_edge1.sort(key=lambda x: len(x[0]), reverse=True)
                off_edge2.sort(key=lambda x: len(x[0]), reverse=True)
                off_edge1, off_edge2 = off_edge1[1:], off_edge2[1:]
                off1, off2 = [], []
                for r in off_edge1:
                    off1 = off1 + r[0]
                for r in off_edge2:
                    off2 = off2 + r[0]
                for r in ab_set:
                    for c in r[0]:
                        if c in off1:
                            e_set1.append(r)
                            break
                    for c in r[0]:
                        if c in off2:
                            e_set2.append(r)
                            break
                return e_set1, e_set2
            elif block_type == 'rand':
                e_set1, e_set2 = [], []
                for i in ab_set:
                    if random.random() > 0.5:
                        e_set1.append(i)
                    if random.random() > 0.5:
                        e_set2.append(i)
                return e_set1, e_set2
            elif block_type == 'big':
                rk = [len(i) for i in ab_set]
                rk = [i / sum(rk) for i in rk]
                e_set = np.random.choice(list(range(len(rk))), p=rk, replace=False, size=int(len(rk) / 2))
                e_set = [ab_set[i] for i in e_set]
                return e_set, e_set
            elif block_type == 'small':
                rk = [len(i) for i in ab_set]
                rk = [1 / i for i in rk]
                rk = [i / sum(rk) for i in rk]
                e_set = np.random.choice(list(range(len(rk))), p=rk, replace=False, size=int(len(rk) / 2))
                e_set = [ab_set[i] for i in e_set]
                return e_set, e_set
            elif block_type == 'rate':
                e_set = np.random.choice(list(range(len(ab_set))), replace=False, size=int(len(ab_set) * 4 / 10))
                e_set = [ab_set[i] for i in e_set]
                return e_set, e_set
            elif block_type == 'self-adaption':
                pa_score, pb_score = parent1.score, parent2.score
                pa_rate = (self.best.score - pa_score + 0.1 * self.worse.score) / (self.best.score - 0.9 * self.worse.score)
                pb_rate = (self.best.score - pb_score + 0.1 * self.worse.score) / (self.best.score - 0.9 * self.worse.score)
                pa_rate, pb_rate = pa_rate * 0.4 + 0.1, pb_rate * 0.4 + 0.1
                e_set1 = np.random.choice(list(range(len(ab_set))), replace=False, size=max(1, int(len(ab_set) * pa_rate)))
                e_set2 = np.random.choice(list(range(len(ab_set))), replace=False, size=max(1, int(len(ab_set) * pb_rate)))
                e_set1, e_set2 = [ab_set[i] for i in e_set1], [ab_set[i] for i in e_set2]
                return e_set1, e_set2
            else:
                raise TypeError('undefined block_type')

    def intersect_LS(self, routes):
        routes = self.intersection_fix(routes)
        while 1:
            distance_list = [calculate_distance(self.Distance, i) for i in routes]
            r = sum(distance_list) / self.sale_num
            alpha = 0.9
            if max(distance_list) > r * alpha and len(routes[distance_list.index(max(distance_list))]) > 4:
                routes = self.GGASS_increase(routes)
            else:
                break
        while len(routes) > self.sale_num:
            routes = self.decrease_circle(routes)
        while len(routes) < self.sale_num:
            routes = self.GGASS_increase(routes)
        return routes

    def mutation(self):
        for i in range(self.pop_size):
            temp = deepcopy(self.population[i])
            if random.random() < self.pm:
                if random.random() > 0.5:
                    temp.gene, c = self.delete_city(temp.gene)
                    temp.gene = self.insert_tour(temp.gene, [c])
                else:
                    r = random.randint(0, self.sale_num - 1)
                    index1 = random.randint(0, len(temp.gene[r]) - 1)
                    index2 = random.randint(index1, len(temp.gene[r]) - 1)
                    tour = temp.gene[r][index1:index2]
                    temp.gene[r] = temp.gene[r][:index1] + temp.gene[r][index2:]
                    if tour:
                        temp.gene = self.insert_tour(temp.gene, tour)
            self.population[i] = temp if temp.verification(depot=self.depot) else self.population[i]

    def big_circle(self, routes, pick_type='difference'):
        if pick_type == 'mean':
            distance_list = [calculate_distance(self.Distance, i) for i in routes]
            r = sum(distance_list) / self.sale_num
            alpha = 0.9
            if max(distance_list) > r * alpha and len(routes[distance_list.index(max(distance_list))]) > 4:
                return True
        elif pick_type == 'difference':
            distance_list = [calculate_distance(self.Distance, i) for i in routes]
            r = max(distance_list) / min(distance_list)
            alpha = 1.3
            if r > alpha and len(routes[distance_list.index(max(distance_list))]) > 4:
                return True
        else:
            raise TypeError("illegal pick_type")
        return False

